import java.util.*;

public class Solution756 {

    boolean flag=false;

    public boolean pyramidTransition(String bottom, List<String> allowed) {
        Map<String,List<String>> map=new HashMap<>();
        for (String s : allowed) {
            String first=s.substring(0,2);
            map.putIfAbsent(first,new ArrayList<>());
            map.get(first).add(s.substring(2));
        }
        dfs(bottom,map);
        return flag;
    }

    private void dfs(String bottom, Map<String, List<String>> map) {
        if (bottom.length()==1){
            flag=true;
            return;
        }
        List<String> list=new ArrayList<>();
        dd(bottom,0,map,new StringBuilder(),list);
        for (String s : list) {
            dfs(s,map);
            if (flag){
                return;
            }
        }
    }

    private void dd(String bottom, int cur, Map<String, List<String>> map, StringBuilder stringBuilder, List<String> list) {
        if (cur==bottom.length()-1){
            list.add(stringBuilder.toString());
            return;
        }
        String tt=bottom.substring(cur,cur+2);
        if (map.containsKey(tt)){
            List<String> l=map.get(tt);
            for (String s : l) {
                stringBuilder.append(s);
                dd(bottom,cur+1,map,stringBuilder,list);
                stringBuilder.deleteCharAt(stringBuilder.length()-1);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution756().pyramidTransition("AABA", Arrays.asList("AAA", "AAB", "ABA", "ABB", "BAC")));
    }
}
